#include <iostream>
#include <vector>

#define fup(x,l,r) for (int x = l; x <= r; ++ x)
#define fdn(x,r,l) for (int x = r; x >= l; -- x)

using namespace std;

const int N = 35;

int l, r, k, b;
int f[N][N];

void init() {
    fup(i, 0, N)
        fup(j, 0, i) {
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
        }
}

int dp(int n) {
    if (!n) return 0;
    
    vector<int> nums;
    while (n) nums.push_back(n % b), n /= b;
    
    int res = 0, last = 0;
    fdn(i, nums.size() - 1, 0) {
        int x = nums[i];
        if (x) {
            res += f[i][k - last];
            if (x > 1) {
                if (k - last - 1 >= 0) res += f[i][k - last - 1];
                break;
            }
            else {
                last ++ ;
                if (last > k) break;
            }
        }
        if (!i && last == k) res ++ ;
    }
    
    return res;
}

int main() {
    init();
    scanf("%d%d%d%d", &l, &r, &k, &b);
    
    cout << dp(r) - dp(l - 1) << endl;
    
    return 0;
}